package subject_set.offer100;

import java.util.HashMap;
import java.util.Map;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
/**
 * @author haomin
 * @date 2022/10/17 16:35
 **/
public class Offer35 {
    // Map
    class Solution1 {
        public Node copyRandomList(Node head) {
            if(head == null) return head;
            Map<Node, Node> map = new HashMap<>();
            for(Node node = head, newNode = null; node != null; node = node.next){
                newNode = new Node(node.val);
                map.put(node, newNode);
            }
            for(Node node = head; node != null; node = node.next){
                map.get(node).next = map.get(node.next);
                map.get(node).random = map.get(node.random);
            }
            return map.get(head);
        }
    }
    // 1-2-3 -> 1-1-2-2-3-3
    class Solution {
        public Node copyRandomList(Node head) {
            if(head == null) return head;
            for(Node node = head, newNode = null; node != null; node = node.next.next){
                newNode = new Node(node.val);
                newNode.next = node.next;
                node.next = newNode;
            }
            for(Node node = head; node != null; node = node.next.next){
                if(node.random != null)
                    node.next.random = node.random.next;
            }
            Node second = head.next;
            for(Node node = head, next = null; node != null && node.next != null;){
                next = node.next;
                node.next = next.next;
                node = next;
            }
            return second;
        }
    }
}